package cn.lintcode;


/**
 * @author labvi
 * @version 1.0.0
 * 是否是平衡二叉树
 */
public class IsBlanceTree {
    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    public boolean isBalanced(TreeNode root) {
        // write your code here
        if (null == root) {
            return true;
        }
        boolean[] flag = new boolean[1];
        getHeight(root,flag);
        return flag[0];
    }

    public int getHeight(TreeNode root, boolean[] flag){
        if (root == null) {
            return 0;
        }
        int l = getHeight(root.left,flag);
        int r = getHeight(root.right,flag);
        if (Math.abs(l-r) > 1) {
            flag[0] = false;
        }
        return Math.max(l,r)+1;
    }
}
